// 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
// 思路，
// 只需要排序k个元素，本题要用小顶堆，如果用大顶堆，每次弹出堆顶都把最大的元素弹出去了
// 先要构造大小为k的小顶堆，然后把剩余的元素从k位置开始，跟堆顶元素比较，如果比堆顶大，则移除堆顶，把该元素放到堆顶，进行headAdjust，调整为小顶堆，最终剩下来的小顶堆就是top k的元素

class HeapQueue {
    arr = []
    map = null
    constructor(arr, map) {
        this.arr = arr
        this.map = map
    }
    heapify(k) {
        for (let i = Math.floor((k - 1) / 2); i >= 0; i--) {
            this.heapAdjust(i, k-1)
        }
    }
    heapAdjust(start, end) {
        let left = 2 * start + 1
        let right = left + 1
        while (left <= end) {
            let target = start
            if (this.map.get(this.arr[left]) < this.map.get(this.arr[target])) {
                target = left
            }
            if (right <= end && this.map.get(this.arr[right]) < this.map.get(this.arr[target])) {
                target = right
            }
            if (target === start) {
                break
            }

            [this.arr[start], this.arr[target]] = [this.arr[target], this.arr[start]];
            start = target
            left = 2 * start + 1
            right = left + 1
        }
    }
    getResult(k) {
        this.heapify(k)
        for (let i = k; i < this.arr.length; i++) {
            if (this.map.get(this.arr[i]) > this.map.get(this.arr[0])) {
                [this.arr[i], this.arr[0]] = [this.arr[0], this.arr[i]];
                this.heapAdjust(0, k - 1)
            }        
        }
        return this.arr.slice(0, k)
    }
}

function topKFrequent(nums,k) {
    let map = new Map
    for (const item of nums) {
        map.set(item, (map.get(item) || 0) + 1)
    }
    let arr = [...new Set(nums)]
    let heapQueue = new HeapQueue(arr, map)
    return heapQueue.getResult(k)
}

nums = [4,4,4,4,4,1,1,1,2,2,3], k = 2
nums =
[4,1,-1,2,-1,2,3]
console.log(topKFrequent(nums, k))